package com.hyb.algorithm.data.struct.tree;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: huyanbing
 * @Date: 2021/8/11 11:15 上午
 * <p>
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 * <p>
 * 从前序与中序遍历序列构造二叉树
 * <p>
 * Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * Output: [3,9,20,null,null,15,7]
 * <p>
 * Input: preorder = [-1], inorder = [-1]
 * Output: [-1]
 * <p>
 * ----3
 * ---9---20
 * ------15  7
 */
public class BuildTree {

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        int n = preorder.length;
        Map<Integer, Integer> inIndexMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            inIndexMap.put(inorder[i], i);
        }


        return buildTree(preorder, 0, n - 1, 0, n - 1, inIndexMap);

    }


    /**
     * 对于 前序遍历 【根节点，左节点，右节点】
     * 对于 中序遍历 【左节点，根节点，右节点】
     *
     * @param preorder
     * @param preStart
     * @param preEnd
     * @param inStart
     * @param inEnd
     * @param inIndexMap
     * @return
     */
    public TreeNode buildTree(int[] preorder, int preStart, int preEnd,
                              int inStart, int inEnd, Map<Integer, Integer> inIndexMap) {

        if(preStart>preEnd||inStart>inEnd){
            return null;
        }

        //前序数组的第一个就是根节点
        TreeNode root = new TreeNode(preorder[preStart]);

        //找到中序排序数组的索引位置
        int rootIndex = inIndexMap.get(root.val);

        //计算左子树个数
        int leftSize = rootIndex - inStart;

        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 leftSize」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = buildTree(preorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1, inIndexMap);

        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = buildTree(preorder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd, inIndexMap);

        return root;


    }

}
